// https://www.lintcode.com/problem/find-all-anagrams-in-a-string/

public class Solution {
    /**
     * @param s: a string
     * @param p: a string
     * @return: a list of index
     */
    public List<Integer> findAnagrams(String s, String p) {
        // write your code here
        List<Integer> ret = new ArrayList<>();
        int len_s = s.length(), len_p = p.length();
        if (len_s < len_p) {
            return ret;
        }
        HashMap<Character, Integer> map_s = new HashMap<>();
        HashMap<Character, Integer> map_p = new HashMap<>();
        buildMap(map_s, s, 0, len_p);
        buildMap(map_p, p, 0, len_p);
        if (map_s.equals(map_p)) {
            ret.add(0);
        }
        for (int i = 1; i < (len_s - len_p + 1); ++i) {
            updateMap(map_s, s.charAt(i - 1), 'r');
            updateMap(map_s, s.charAt(i + len_p - 1), 'a');
            if (map_p.containsKey(s.charAt(i))) {
                if (map_s.equals(map_p)) {
                    ret.add(i);
                }
            }
        }
        return ret;
    }
    
    protected void buildMap(HashMap<Character, Integer> map, String s, int start, int end) {
        for (int i = start; i < end; ++i) {
            updateMap(map, s.charAt(i), 'a');
        }
    }
    
    protected void removeKey(HashMap<Character, Integer> map, Character key) {
        Iterator<Character> iter = map.keySet().iterator();
        while (iter.hasNext()){
            if(iter.next().equals(key)){
                iter.remove();
                break;
            }
        }
    }
    
    protected void updateMap(HashMap<Character, Integer> map, Character c, Character op) {
        // a = add, r = remove
        if (op == 'r') {
            int v = map.get(c);
            if (v > 1) {
                map.put(c, v - 1);
            } else {
                removeKey(map, c);
            }
        } else {
            if (!map.containsKey(c)) {
                map.put(c, 0);
            }
            map.put(c, map.get(c) + 1);
        }
    }
}